//
// Created by ASUS on 2024/7/3/星期三.
//
/*
给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：
给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。
如果按照上述要求无法得到任何整数，请你返回 "0" 。
 */

#include <bits/stdc++.h>
using namespace std;

//记忆化搜索
string largestNumber(vector<int>& cost, int target) {
	int n = cost.size();
	vector<int> memo(target + 1, INT_MIN/2);
	//花费j能买到最长数字长度
	function<int(int)> dfs = [&](int j) -> int {
		if (j == 0)//没钱了，买不了了，剩余长度只能为0
			return 0;
		if (memo[j] != INT_MIN/2)//已经计算过了
			return memo[j];
		int res = -1;//没买到不合法值和记忆化不合法值不能相同，因为这个状态已经走过了
		for (int i = 0; i < n; i++) {
			//如果当前数位能买到，且能买到更长的数字，则更新res
			if (j >= cost[i] && dfs(j - cost[i]) != -1) {
				res = max(res, dfs(j - cost[i]) + 1);
			}
		}
		//记忆化
		return memo[j] = res;
	};
	//没买到
	if (dfs(target) == -1) return "0";

	string ans;

	function<void(int)> print_ans = [&](int j) {
		if (j == 0) return;
		int final_res = dfs(j);//算出当前状态值
		//从大到小遍历，这样才是最大值
		for (int i = n - 1; i >= 0; i--) {
			if (j >= cost[i] &&  dfs(j - cost[i])!= -1) {
				//能买到
				if (final_res == dfs(j - cost[i])+ 1) {
					ans.push_back('1' + i );//记录答案
					print_ans(j - cost[i]);//继续递归
					break;//退出当前循环，因为每一位只能有一个数字
				}
			}
		}
	};
	print_ans(target);
	return ans;
}

//递推
string largestNumber1(vector<int>& cost, int target) {
	int n = cost.size();
	vector<int> f(target + 1, INT_MIN / 2);
	f[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = cost[i]; j <= target; j++) {
			f[j] = max(f[j], f[j - cost[i]] + 1);
		}
	}
	if (f[target] < 0)
		return "0";
	string ans;
	int j = target;
	for (int i = n - 1; i >= 0; i--) {
		for (; j >= cost[i]; j -= cost[i]) {
			if (f[j] == f[j - cost[i]] + 1) {
				ans += '1' + i;
			} else {
				break;
			}
		}
	}
	return ans;
}
